#pragma once


#include "IncidenceGraph.h"


#include <map>
#include <list>
#include <algorithm>
#include <iostream>
using namespace std;


static const double INFINITY = numeric_limits<double>::infinity();


struct PathVertex
{
	int current;
	int previous;
	double distance;

	PathVertex() : current(-1), previous(-1), distance(INFINITY) { }
	PathVertex(int c, int p, double d) : current(c), previous(p), distance(d) {}
};


class Dijkstra
{
public:
	Dijkstra(const IncidenceGraph& graph);
	~Dijkstra();

	bool CalculateShortestDistances(int source);

	list<PathVertex> GetShortestPath(int target);
	double GetDistance(int target);

	int Source() const { return source; }

private:
	const IncidenceGraph& graph;
	map<int, PathVertex> shortestPaths;
	int source;
};

